Test Series - Data Structure

3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117

Test Number 101/115

Q: Which of the following problems occur due to linear probing?
A. Primary collision
B. Secondary collision
C. Separate chaining
D. Extendible hashing
Solution: Primary collision occurs due to linear probing technique. It is overcome using a quadratic probing technique.
Q: How many probes are required on average for insertion and successful search?
A. 4 and 10
B. 2 and 6
C. 2.5 and 1.5
D. 3.5 and 1.5
Solution: Using formula, the average number of probes required for insertion is 2.5 and for a successful search, it is 1.5.
Q: What is the load factor for an open addressing technique?
A. 1
B. 0.5
C. 1.5
D. 0
Solution: The load factor for an open addressing technique should be 0.5. For separate chaining technique, the load factor is 1.
Q: Which of the following is not a collision resolution strategy for open addressing?
A. Linear probing
B. Quadratic probing
C. Double hashing
D. Rehashing
Solution: Linear probing, quadratic probing and double hashing are all collision resolution strategies for open addressing whereas rehashing is a different technique.
Q: In linear probing, the cost of an unsuccessful search can be used to compute the average cost of a successful search.
A. True
B. False
C. ...
D. ...
Solution: Using random collision resolution algorithm, the cost of an unsuccessful search can be used to compute the average cost of a successful search.
Q: Which of the following is the correct function definition for linear probing?
A. F(i)= 1
B. F(i)=i
C. F(i)=i2
D. F(i)=i+1
Solution: The function used in linear probing is defined as, F(i)=I where i=0,1,2,3….,n.
Q: ___________ is not a theoretical problem but actually occurs in real implementations of probing.
A. Hashing
B. Clustering
C. Rehashing
D. Collision
Solution: Clustering is not a theoretical problem but it occurs in implementations of hashing. Rehashing is a kind of hashing.
Q: What is the hash function used in linear probing?
A. H(x)= key mod table size
B. H(x)= (key+ F(i2)) mod table size
C. H(x)= (key+ F(i)) mod table size
D. H(x)= X mod 17
Solution: The hash function used in linear probing is defined to be H(x)= (key+ F(i)) mod table size where i=0,1,2,3,…,n.
Q: Hashing can be used in online spelling checkers.
A. True
B. False
C. ...
D. ...
Solution: If misspelling detection is important, an entire dictionary can be pre-hashed and words can be checked in constant time.
Q: In the following given hash table, use linear probing to find the location of 49.

0	
1	
2	
3	
4	
5	
6	
7	
8	18
9	89
A. 7
B. 6
C. 2
D. 0
Solution: Initially, collision occurs while hashing 49 for the first time.
Hence, after setting f(i)=1, the hashed location is found to be 0.

You Have Score    /10